package com.mzy.linear_struct.subject;

import java.util.HashMap;
import java.util.Map;

/**
 * @Author: codermzy
 * @Date: 2024/04/28/下午1:09
 * @Description:
 */
public class 爬楼梯70 {
    static class Solution {
        public int climbStairs(int n) {
            // 1. 定义状态
            // key 为第n阶台阶，value为n阶台阶的跳法
            Map<Integer, Integer> dp = new HashMap<>();

            // 2. 确认状态转移方程
            // 第n阶台阶 = 第 n - 1处的跳法 + n - 2处的跳法
            // 所以：dp[n] = dp[n-1] + dp[n-2]


            // 3. 初始化状态
            // 为了方便起见，我们把 n = 0 设置为1，这样一来， n = 2时，就是 1(n=0时) + 1(n=1时)
            dp.put(0, 1);
            dp.put(1, 1);
            // n = 1 时，有一种跳法
            // n = 2 时，有两种跳法
            // n = 3 时，有三种跳法，即 n = 2 + 1

            for (int i = 2; i <= n; i++) {
                // 4. 计算结果
                int jump = dp.get(i - 1) + dp.get(i - 2);
                dp.put(i, jump);
            }
            return dp.get(n);
        }
    }

    public static void main(String[] args) {

        System.out.println(new Solution().climbStairs(2));
    }
}
